//
// Created by francklinson on 2021/7/6.
//

#include <vector>
#include <iostream>
#include <queue>
#include <climits>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int maxLevelSum(TreeNode *root) {
        if (root == nullptr) return 1;
        queue<TreeNode *> q;
        q.push(root);
        int levelNum = 0;
        int ansLevel = 0;
        int maxLevelSum = INT_MIN;
        while (!q.empty()) {
            ++levelNum; // 层数增加
            int levelSize = q.size();
            int levelSum = 0; // 该层之和
            for (int i = 0; i < levelSize; ++i) {
                auto p = q.front();
                q.pop();
                levelSum += p->val;
                if (p->left != nullptr) q.push(p->left);
                if (p->right != nullptr) q.push(p->right);
            }
            // 更新最大层
            if (levelSum > maxLevelSum) {
                maxLevelSum = levelSum;
                ansLevel = levelNum;
            }
        }
        return ansLevel;
    }
};


int main() {
    auto n1 = TreeNode(1), n2 = TreeNode(7), n3 = TreeNode(0), n4 = TreeNode(7), n5 = TreeNode(-8);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    Solution sol;
    cout << sol.maxLevelSum(&n1) << endl;
    return 0;
}